package tree.PathSum;

import tree.TreeNode;

import java.util.*;

/**
 * @ClassName HasPathSum
 * @Description TODO
 * @Author lenovo
 * @Date 2023-03-16 20:42
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class HasPathSum2 {

    /**
     * 112. 路径总和
     * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回所有集合。
     * <p>
     * 叶子节点 是指没有子节点的节点。
     *
     * @param root
     * @param targetSum
     * @return
     */
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queueNode = new LinkedList<TreeNode>();
        Queue<Integer> queueSum = new LinkedList<Integer>();
        queueNode.offer(root);
        queueSum.offer(0);

        while (!queueNode.isEmpty()) {
            TreeNode node = queueNode.poll();
            int rec = queueSum.poll() + node.val;

            if (node.left == null && node.right == null) {
                if (rec == targetSum) {
                    getPath(node);
                }
            } else {
                if (node.left != null) {
                    map.put(node.left, node);
                    queueNode.offer(node.left);
                    queueSum.offer(rec);
                }
                if (node.right != null) {
                    map.put(node.right, node);
                    queueNode.offer(node.right);
                    queueSum.offer(rec);
                }
            }
        }

        return ret;
    }

    public void getPath(TreeNode node) {
        List<Integer> temp = new LinkedList<Integer>();
        while (node != null) {
            temp.add(node.val);
            node = map.get(node);
        }
        Collections.reverse(temp);
        ret.add(new LinkedList<Integer>(temp));
    }


    private List<Integer> addList(List<Integer> origin, List<Integer> temp) {
        origin.addAll(temp);
        return origin;
    }


    public List<List<Integer>> pathSum1(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();

        depth(result, temp, 0, targetSum, root);
        return result;
    }

    /*
    *
    *     1
    *  2     3
    *
    * */
    private void depth(List<List<Integer>> result, List<Integer> temp, int num, int targetSum, TreeNode root) {
        if (root == null) return;
        num += root.val;
        temp.add(root.val);
        if (root.left == null && root.right == null && num == targetSum) {
            result.add(temp);
        }
        depth(result, new ArrayList<>(temp),num,targetSum,root.left);
        depth(result, new ArrayList<>(temp),num,targetSum,root.right);
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(3);

        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(0);
        TreeNode treeNode3 = new TreeNode(1);
        treeNode.left = treeNode1;
        treeNode.right = treeNode2;
        treeNode2.right = treeNode3;
        HasPathSum2 hasPathSum = new HasPathSum2();
//        System.out.println(hasPathSum.hasPathSum1(treeNode, 5));
        List<List<Integer>> lists = hasPathSum.pathSum1(treeNode, 4);
        for (List<Integer> list : lists) {
            System.out.println();
            for (Integer integer : list) {
                System.out.println(integer);
            }
        }
    }

//    1
//  2   3
}